// 316. 去除重复字母

package Leetcode;

import java.util.Deque;
import java.util.LinkedList;

public class Solution316 {
    public String removeDuplicateLetters(String s) {
        // 统计字符出现的数量
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }

        Deque<Character> stack = new LinkedList<>();
        boolean[] inStack = new boolean[26];

        for (char c : s.toCharArray()) {
            count[c - 'a']--;

            // 如果单调栈中已经存在则直接跳过
            if (inStack[c - 'a'])
                continue;

            // 如果当前不存在该字符
            while (!stack.isEmpty() && stack.peek() > c) {
                // 如果后续没有改字符则停止出栈
                if (count[stack.peek() - 'a'] == 0) {
                    break;
                }
                // 出栈
                inStack[stack.pop() - 'a'] = false;
            }

            stack.push(c);
            inStack[c - 'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.reverse().toString();
    }
}
